package codetop.microsoft.T337;

import util.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: 18362
 * @Create: 2022-08-15 14:28:46 星期一
 */
class Solution {
    private Map<TreeNode, Integer> robbed = new HashMap<>();
    private Map<TreeNode, Integer> notRobbed = new HashMap<>();

    public int rob(TreeNode root) {
        return Math.max(rob(root, false), rob(root, true));
    }

    private int rob(TreeNode root, boolean robRoot) {
        if (root == null)
            return 0;
        if (!robRoot && notRobbed.containsKey(root))
            return notRobbed.get(root);
        int leftNotRob = rob(root.left, false), rightNotRob = rob(root.right, false);
        int leftRob = rob(root.left, true), rightRob = rob(root.right, true);
        int notRobbedRes = leftRob + rightRob, robRes = root.val + leftNotRob + rightNotRob;
        notRobbed.put(root, notRobbedRes);
        robbed.put(root, robRes);
        if (!robRoot)
            return notRobbedRes;
        return Math.max(notRobbedRes, robRes);
    }
}